# -*- coding: utf-8 -*-

"""
    http://projecteuler.net/problem=31
    
    PROBLEM
    
    In England the currency is made up of pound, £, and pence, p, and there
    are eight coins in general circulation:

    1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

    It is possible to make £2 in the following way:

    1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

    How many different ways can £2 be made using any number of coins?

    
    NOTES
    My final solution ended up being pretty much the same procedure with which
    I started but optimized to complete just under 10 minutes.

    
    REFERENCES
    http://en.wikipedia.org/wiki/Dynamic_programming
    
    
    PERFORMANCE
    time <optimized solution at 0x7f34460767d0>: 0.140415 s
    time <brute force solution at 0x7fc930fd8ed8>: 557.367615 s

    
"""
#
# Import
#
import time


#
# Globals / Constants
#
COINAGE = {
    '1p'  : 1,
    '2p'  : 2,
    '5p'  : 5,
    '10p' : 10,
    '20p' : 20,
    '50p' : 50,
    'L1'  : 100,
    'L2'  : 200,
}
COINS = sorted(COINAGE.values())


def timeit(f):
    def timer():
        t0 = time.time()
        returned = f()
        print "time %s: %.6f s" % (f, time.time() - t0)
        return returned
    return timer

def assert_match(value, expected, message=""):
    f = "value %s != expected %s"
    f = message != '' and f + " (%s)" or f + "%s"
    assert value == expected, f % (value, expected, message)


#
# Test Case / Solution
#
#@timeit    
def test_case():
    cases = [
        (1, 1),
        (2, 2),
        (5, 4),
        (10, 11),
        (20, 41)
    ]
    
    for coin, expected in cases:
        combos = change_combos(coin)
        assert_match(combos, expected, coin)
    
    print "test case passed!"

@timeit
def solution():
    return change_combos(200)

#
# Solution Code
#
def change_combos(amount):
    """http://stackoverflow.com/a/4423786/1093087"""
    combos = [1] + [0] * 200
    for coin in COINS:
        for x in xrange(coin, amount+1):
            combos[x] += combos[x-coin]
    return combos[amount]        


def brutish_force(amount):
    
    combo_tracker = dict()
    combo_count = 0
    
    def combinate(i1, i2):
        combos = [c1 + c2 for c1 in combo_tracker.get(i1, []) \
            for c2 in combo_tracker.get(i2, [])]
        return [as_coinset(c) for c in combos]
    
    def get_all_combos():
        for combo_list in combo_tracker.values():
            for combo in combo_list:
                yield combo
    
    def unique(combos):
        unique_combos = []
        all_combos = [c for c in get_all_combos()]
        combos = list(set(combos))
        for combo in combos:
            sorted_combo = as_coinset(combo)
            if sorted_combo not in all_combos:
                unique_combos.append(sorted_combo)
        return unique_combos
    
    for value in range(1, 201):
        stop_at = (value / 2) - 1
        
        # working out the pattern manually I see why this is excluded (no
        # new combos after 1,2), but this sure smells here
        if value == 3:
            continue
        
        if value in COINS:
            value_combos = [value]
        else:
            value_combos = []
        
        for i1 in xrange(value-2, stop_at, -1):
            i2 = value - i1
            value_combos += combinate(i1, i2)
        
        new_combos = unique(value_combos)
        combo_tracker[value] = new_combos
        combo_count += len(new_combos)
            
        #print '>', value, (combo_count,), new_combos, combo_tracker
        print '>', value, (combo_count,)
            
        if value == amount:
            return combo_count
       
def as_coinset(value):
    if type(value) == int:
        return (value,)
    elif type(value) == list:
        return as_coinset(tuple(value))
    elif type(value) == tuple:
        return tuple(sorted(value))
    else:
        raise ValueError("coinset must be int, list, or tuple")


#
# Additional Tests
#


#
# Main
#
if __name__ == '__main__':
    test_case()
    print solution()
